package chapter01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindSubstring {
    //滑动窗口
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res=new ArrayList<>();
        if(words==null||s==null||words.length<1||s.length()< words.length*words[0].length()){
            return res;
        }
        int wordsLength=words[0].length();
        int stringLength=s.length();
        int num=words.length;
        HashMap<String,Integer> strMap=new HashMap<>();
        HashMap<String,Integer> found=new HashMap<>();
        for(String str:words){
            strMap.put(str,strMap.getOrDefault(str,0)+1);
        }
        for(int i=0;i<=stringLength-num*wordsLength;i++){
            found.clear();
            int j=0;
            for(j=0;j<num;j++){
                String str=s.substring(i+j*wordsLength,i+(j+1)*wordsLength);
                if(strMap.containsKey(str)){
                    found.put(str,found.getOrDefault(str,0)+1);
                    if(found.get(str)>strMap.get(str)){
                        break;
                    }
                }else{
                    break;
                }
            }
            if(j==num){
                res.add(i);
            }
        }
        return res;
    }
}
